from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
import math
import sys
import struct
IN = lambda: sys.stdin.readline().rstrip("\r\n")
PN = lambda x: sys.stdout.write(x)
I = lambda: int(IN())
S = lambda: IN().split()
M = lambda: map(int, IN().split())
L = lambda: list(map(int, IN().split()))
G = lambda: map(lambda x: int(x) - 1, IN().split())
def array(shape, value = 0):
if len(shape) == 0:
return value
else:
return [array(shape[1:], value = value) for _ in range(shape[0])]
mod = 1000000007
def qpow(a, b, p = mod):
res = 1
while b:
if b & 1:
res = res * a % p
a = a * a % p
b >>= 1
return res
mod = 998244353
class Comb:
def __init__(self, n, p = mod):
self.__fac = [0 for _ in range(n + 1)]
self.__ifac = [0 for _ in range(n + 1)]
self.__fac[0] = 1
self.__mod = p
for i in range(1, n + 1):
self.__fac[i] = i * self.__fac[i - 1] % self.__mod
self.__ifac[n] = qpow(self.__fac[n], mod - 2)
for i in range(n - 1, -1, -1):
self.__ifac[i] = (i + 1) * self.__ifac[i + 1] % self.__mod
def binom(self, a, b):
if a < b or b < 0:
return 0
return self.__fac[a] * self.__ifac[b] * self.__ifac[a - b] % self.__mod
def fac(self, n):
return self.__fac[n]
def ifac(self, n):
return self.__ifac[n]
a, b, m = M()
n = a + b
e = [0 for _ in range(m + 1)]
deg = [0 for _ in range(n + 1)]
for i in range(1, m + 1):
u, v = M()
v += a
e[i] = (u, v)
deg[u] += 1
deg[v] += 1
ans = max(deg)
match = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
for i in range(1, m + 1):
c1, c2 = 1, 1
u, v = e[i]
while match[u][c1]:
c1 += 1
while match[v][c2]:
c2 += 1
match[u][c1] = v
match[v][c2] = u
if c1 == c2:
continue
c0, w = c2, v
while w != 0:
match[w][c1], match[w][c2] = match[w][c2], match[w][c1]
w = match[w][c0]
c0 ^= c1 ^ c2
def getans(i):
u, v = e[i]
for j in range(1, ans + 1):
if match[v][j] == u:
return j
return -1
print(ans)
for i in range(1, m + 1):
print(getans(i), end = ' ')
// hiensumi: Maybe, success will come tomorrow. Thus, just keep trying! =) "Z/x
#include "bits/stdc++.h"
#define fod(i,a,b) for(int i = a;i <= b; i++)
#define fok(i,a,b) for(int i = a;i >= b; i--)
#define ll long long
#define int long long
#define fi first
#define se second
#define mask(i) (1LL<<(i))
#define BITpos(a,i) ((a >> i) & 1LL)
#define pb push_back
#define el '\n'
#define all(v) v.begin(), v.end()
#define odd(i) (i & 1LL)
using namespace std;
typedef pair<int, int> ii;
const int MOD = 1e9 + 7;
inline void kill(){cerr << "\nTime: " << clock() << "ms\n"; cerr << "⏁⊑⟒ ⋔⍜⍜⋏ ⍙⏃⌇ ⌇⍜ ⏚⟒⏃⎍⏁⟟⎎⎍⌰ ⏁⊑⏃⏁ ⏁⊑⟒⍀⟒ ⍙⏃⌇ ⏃ ⋔⟟⍀⍀⍜⍀ ⟟⋏ ⏁⊑⟒ ⍜☊⟒⏃⋏.\n"; exit(0);}
inline void add(int &x, int y, int mod = MOD) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod;}
inline void mul(int &x, int y, int mod = MOD) { x = (x * 1LL * y) % mod;}
inline int bpow(int x, int y, int mod = MOD) { int ans = 1; while (y) { if (y & 1) mul(ans, x, mod); mul(x, x, mod); y >>= 1;} return ans;}
inline int bp(int a, int b){int res = 1; while (b > 0) {if (b & 1) res = res * a; a = a * a; b >>= 1; } return res;}
inline int Inv(int x, int mod = MOD) { return bpow(x, mod - 2, mod);}
inline int Div(int x, int y, int mod = MOD) { int tmp = x; mul(tmp, Inv(y, mod), mod); return tmp;}
template<class T> bool mini(T& a,T b){return (a>=b)?a=b,1:0;}
template<class T> bool maxi(T& a,T b){return (a<=b)?a=b,1:0;}
struct point{int x, y;};
struct edge{int u, v, c;};
//int find(int u){if (lab[u] < 0) return u; return lab[u] = find(lab[u]);}
//bool join(int u, int v){u = find(u);v = find(v);if(u == v) return 0;if(lab[u] > lab[v]) swap(u,v);lab[u] += lab[v];lab[v] = u; return 1;}
const ll INF = 1e18, base = 1e6 + 5, multitest = 0;
//"Life is a daring adventure or it is nothing at all." -Helen Keller...
//"Success isn't determined by how many times you win, but by how you play the week after you lose." -Pele...
#define name ""
#define ld long double
// remember to reset value for multitestcase
// she is your motivation!!!
void init(){
}
int a, b, m, match[base];
vector <int> g[base];
vector <ii> hn;
void inp(){
cin >> a >> b >> m;
fod(i,1,m){
int u, v; cin >> u >> v;
g[u].pb(v + a);
g[v+a].pb(u);
hn.pb(ii(u,v));
}
}
namespace sub_task1{
int ans[1005][1005], dd[base];
bool konig(int u, int cnt, int color){
if(dd[u] == cnt) return 0;
dd[u] = cnt;
for(int v : g[u]){
bool ch = u > a and g[match[v]].size() < color;
if(ch or match[v] == 0 or konig(match[v], cnt, color)){
if(ch) match[match[v]] = 0;
match[v] = u;
match[u] = v;
return 1;
}
}
return 0;
}
void solve(){
int res = 0;
fod(i,1,a+b) maxi(res, (int)g[i].size());
cout << res << el;
int cnt = 0;
fok(color, res, 1){
fod(i,1,a+b) match[i] = 0;
fod(i,1,a+b){
if(match[i] == 0 and g[i].size() == color){
konig(i,++cnt,color);
}
}
fod(u,1,a) if(match[u] != 0){
int v = match[u];
ans[u][v-a] = color;
g[u].erase(find(all(g[u]), v));
g[v].erase(find(all(g[v]), u));
}
}
for(auto [u,v] : hn){
cout << ans[u][v] << " ";
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(name".inp", "r")){
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
int Test = 1; if(multitest) cin >> Test;
init();
while(Test--){
inp();
sub_task1 :: solve();
}
kill();
}
/*
Trú mưa nơi gốc cây ngày xưa
Để nhìn em lần cuối trong mưa
Để nắm tay đưa em đi về
Chốn mộng mơ...
Có hôm mây gió chợt ca vang
Nụ cười em như nắng mùa thu sang
Làm lòng tôi xao xuyến mà lang thang
Nghĩ về em...
Mình tôi thao thức
mình tôi day dứt
Cớ sao em không về với tôi
Mình tôi thao thức
mình tôi day dứt
Cớ sao em không cười với tôi
Gió mang câu ca về nơi đây
gió mang câu ca về với đời em
Nắng mang câu thơ về nơi đây
chính em mang thơ về với tình ta ...
Chiếc radio của em
Và từng ly trà đá ly kem
Cùng hát lên câu ca êm đềm
giữa mùa yêu
Những bông hoa xanh ngoài hiên
Vào buổi chiều tràn nắng an nhiên
Ta ngồi bên cạnh nhau
ngắm mùa thu sang...
*/
2099. Find Subsequence of Length K With the Largest Sum | 1608A - Find Array |
416. Partition Equal Subset Sum | 1446. Consecutive Characters |
1618A - Polycarp and Sums of Subsequences | 1618B - Missing Bigram |
938. Range Sum of BST | 147. Insertion Sort List |
310. Minimum Height Trees | 2110. Number of Smooth Descent Periods of a Stock |
2109. Adding Spaces to a String | 2108. Find First Palindromic String in the Array |
394. Decode String | 902. Numbers At Most N Given Digit Set |
221. Maximal Square | 1200. Minimum Absolute Difference |
1619B - Squares and Cubes | 1619A - Square String |
1629B - GCD Arrays | 1629A - Download More RAM |
1629C - Meximum Array | 1629D - Peculiar Movie Preferences |
1629E - Grid Xor | 1629F1 - Game on Sum (Easy Version) |
2148. Count Elements With Strictly Smaller and Greater Elements | 2149. Rearrange Array Elements by Sign |
2150. Find All Lonely Numbers in the Array | 2151. Maximum Good People Based on Statements |
2144. Minimum Cost of Buying Candies With Discount | Non empty subsets |